package 牛客网在线编程题库;

import java.util.HashMap;

/**
 * 题目描述
 * 给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。
 * 示例1
 * 输入
 * [2,3,4,5]
 * 返回值
 * 4
 * 示例2
 * 输入
 * [2,2,3,4,3]
 * 返回值
 3
 */

public class _最长无重复子串 {
    public static void main(String[] args) {
        int[] arr = {2, 2, 3, 4, 3};
        int target = maxLength(arr);
        System.out.println(target);
    }

    /**
     * 滑动窗口法
     * @param arr
     * @return
     */
    public static int maxLength (int[] arr) {
        // write code here
        // 滑动窗口
        HashMap<Integer, Integer> window = new HashMap<>();
        // 最大长度
        int maxLen = 1;
        // 双指针，即为滑动窗口的左右边界
        for (int left = 0, right = 0 ; right < arr.length ; right++) {
            // 如果当前元素在窗口中有重复的
            if (window.containsKey(arr[right])) {
                // 改变左指针的位置
                left = Math.max(left, window.get(arr[right]) + 1);
            }
            // 更新最大长度值
            maxLen = Math.max(maxLen, right - left + 1);
            // 如果没有重复的，直接将元素和索引放入窗口内即可
            window.put(arr[right], right);
        }
        return maxLen;
    }
}
